from collections import defaultdict
from typing import List

# 统计前缀和出现的次数
# 1.使用「前缀和」表示子数组的累加和：对于数组中的每个位置 i，我们计算前缀和 prefix[i]，表示从数组开始到当前位置的累加和。
# 2.如果一个子数组的和为 goal，那么：prefix[j]−prefix[i]=goal， 等价于：prefix[i]=prefix[j]−goal
# 其中，j 是当前位置，i 是子数组的起始位置。
#
# 3.使用一个哈希表 count 存储每个前缀和出现的次数，遍历数组时：
# 检查 prefix[j]−goal 是否在哈希表中。
# 如果存在，则说明以当前元素结尾的子数组满足条件，将对应的次数加到结果中。
# 更新哈希表，记录当前前缀和的出现次数。
class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        # 用来存储前缀和出现的次数
        prefix_count = defaultdict(int)
        prefix_count[0] = 1  # 初始情况下，前缀和为 0 的情况出现 1 次

        prefix_sum = 0  # 当前前缀和
        result = 0  # 满足条件的子数组个数

        for num in nums:
            prefix_sum += num  # 更新前缀和

            # 检查是否存在 prefix_sum - goal
            if prefix_sum - goal in prefix_count:
                result += prefix_count[prefix_sum - goal]

            # 更新当前前缀和的出现次数
            prefix_count[prefix_sum] += 1

        return result
